﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0127_PreorderTraversal : IAlgorithm
    {
        // 144. 二叉树的前序遍历

        // 给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

        // 提示：
        //  树中节点数目在范围[0, 100] 内
        //  -100 <= Node.val <= 100

        // 进阶：递归算法很简单，你可以通过迭代算法完成吗？

        public void Test()
        {
            // 算法参数定义
            var root = new TreeNode(1, new TreeNode(2), new TreeNode(3));
            // 算法执行与打印
            var res = PreorderTraversal1(root);
            foreach (var item in res)
            {
                Console.Write(item + " ");
            }
        }

        // 算法
        public IList<int> PreorderTraversal(TreeNode root)
        {
            var res = new List<int>();
            if (root == null)
                return res;
            Helper(root, res);
            return res;
        }
        private void Helper(TreeNode root, List<int> res)
        {
            if (root == null)
                return;
            res.Add(root.val);
            Helper(root.left, res);
            Helper(root.right, res);
        }

        // 非递归
        public IList<int> PreorderTraversal1(TreeNode root)
        {
            var res = new List<int>();
            if (root == null)
                return res;
            var stack = new Stack<TreeNode>();
            stack.Push(root);
            while (stack.Count > 0)
            {
                var temp = stack.Pop();
                res.Add(temp.val);
                if (temp.right != null)
                    stack.Push(temp.right);
                if (temp.left != null)
                    stack.Push(temp.left);
            }
            return res;
        }
    }
}
